#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3, INF = 1e9;
int d[maxn][maxn], N, M;
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    fill(d, d+maxn*maxn, INF);
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b, w; cin >> a >> b >> w;
        d[a][b] = w;
    }
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= k; ++i)
            for (int j = 1; j <= k; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    return 0;
}